COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr
C00003 00003	%folio 638 galley 6 (C) Addison-Wesley 1978	*
C00012 00004	\vfill\eject
C00020 00005
C00021 ENDMK
C⊗;
\input acphdr
\runninglefthead{ARITHMETIC---FIRST PROOFS $\copyright$ 1978}
\runningrighthead{ARITHMETIC---FIRST PROOFS $\copyright$ 1978}
\section{4.x}
\setcount0 701
\tenpoint
%folio 638 galley 6 (C) Addison-Wesley 1978	*
\subsectionbegin{Reversion of series}
The transformation of power series that
is perhaps of greatest interest is called ``reversion of series.''
This problem is to solve the equation
$$z = t + V↓2t↑2 + V↓3t↑3 + V↓4t↑4 +\cdots \eqno(10)$$
for $t$, obtaining the coefficients of the power series
$$t = z + W↓2z↑2 + W↓3z↑3 + W↓4z↑4 +\cdotss.\eqno (11)$$

Several interesting ways to achieve such a reversion
are known. We might say that the ``classical'' method is one
based on Lagrange's remarkable inversion formula [{\sl M\'emoires
Acad.\ Royale des Sciences et Belles-Lettres de Berlin \bf 24}
(1768), 251--326], which states that
$$W↓n = U↓{n-1}/n,$$
if
$$U↓0 + U↓1t + U↓2t↑2 +\cdots = (1 + V↓2t +
V↓3t↑2 +\cdotss)↑{-n}.\eqno (12)$$
For example, we have $(1 - t)↑{-5} = {4\choose 4}
+ {5\choose 4}t + {6\choose 4}t↑2 +\cdotss$; hence $W↓5$ in
the reversion of $z = t - t↑2$ is equal to ${8\choose 4}/5
= 14$. This checks with the formulas for enumerating binary trees
in Section 2.3.4.4.

Relation (12) shows that we can revert the series
(10) if we compute $(1 + V↓2t + V↓3t↑2 +\cdotss)↑{-n}$
for $n = 1$, 2, 3, $\ldotss\,$. A straightforward application of
this idea would lead to an on-line power-series algorithm that
uses approximately $N↑3/2$ multiplications to find $N$ coefficients,
but Eq.\ (9) makes it possible to work with only the first $n$
coefficients of $(1 + V↓2t + V↓3t↑2 +\cdotss)↑{-n}$,
obtaining an on-line algorithm that requires only about $N↑3/6$
multiplications.

\algbegin Algorithm L (Lagrangian power-series
reversion). This on-line algorithm inputs the value of $V↓n$
in (10) and outputs the value of $W↓n$ in (11), for $n = 2$,
3, 4, $\ldotss$, $N$.\xskip (The number $N$ need not be specified in
advance; some other termination condition may be substituted.)

\algstep L1. [Initialize.] Set $n ← 1$, $U↓0
← 1$.\xskip (The relation
$$(1 + V↓2t + V↓3t↑2 +\cdotss)↑{-n}
= U↓0 + U↓1t +\cdots + U↓{n-1}t↑{n-1} + O(t↑n).\eqno(13)$$
will be maintained throughout this algorithm.)

\topinsert{\vskip 34mm
\ctrline{\caption Fig.\ 16. Power-series reversion by Algorithm L.}}

\algstep L2. [Input $V↓n$.] Increase $n$ by 1. If
$n > N$, the algorithm terminates; otherwise input the next
coefficient, $V↓n$.

\algstep L3. [Divide.] Set $U↓k ← U↓k - U↓{k-1}V↓2 -\cdots
- U↓1V↓k - V↓{k+1}$, for $k = 1$, 2, $\ldotss$, $n - 2$ (in
this order); then set
$$U↓{n-1} ← -2U↓{n-2}V↓2 - 3U↓{n-3}V↓3 -\cdots
- (n - 1)U↓1V↓{n-1} - nV↓{n-1}.$$
$\biglp$We have thereby divided $U(z)$ by
$V(z)/z$; cf.\ (3) and (9).$\bigrp$

\algstep L4. [Output $W↓n$.] Output $U↓{n-1}/n$
(which is $W↓n$) and return to L2.\quad\blackslug

\yyskip When applied to the example $z = t - t↑2$,
the computation in Algorithm L is
$$\vjust{\halign{$\ctr{#}$\qquad⊗$\hfill#$\qquad⊗$\hfill#$\qquad⊗$\hfill#$\qquad
⊗$\hfill#$\qquad⊗$\hfill#$\qquad⊗$\hfill#$\qquad⊗$\hfill#$\cr
n⊗V↓n\hfill⊗U↓0\hfill⊗U↓1\hfill⊗U↓2\hfill⊗U↓3\hfill⊗U↓4\hfill⊗W↓n\cr
\noalign{\vskip3pt}
1⊗1⊗1⊗⊗⊗⊗⊗1\cr
2⊗-1⊗1⊗2⊗⊗⊗⊗1\cr
3⊗0⊗1⊗3⊗6⊗⊗⊗2\cr
4⊗0⊗1⊗4⊗10⊗20⊗⊗5\cr
5⊗0⊗1⊗5⊗15⊗35⊗70⊗14\cr}}$$
Exercise 8 shows a slight modification of Algorithm
L will solve a considerably more general problem with only a
little more effort.

Let us now consider solving the equation
$$U↓1z + U↓2z↑2 + U↓3z↑3 +\cdots = t + V↓2t↑2 +
V↓3t↑3 +\cdots \eqno (14)$$
for $t$, obtaining the coefficients of the power
series
$$t = W↓1z + W↓2z↑2 + W↓3z↑3 + W↓4z↑4 +\cdotss.\eqno (15)$$
Eq.\ (10) is the special case $U↓1 = 1$, $U↓2 = U↓3
=\cdots = 0$. If $U↓1 ≠ 0$, we may assume that $U↓1
= 1$, if we replace $z$ by $(U↓1z)$; but we shall consider the
general equation (14), since $U↓1$ might equal zero.

\algbegin Algorithm T (General power-series reversion).
This on-line algorithm inputs the values of $U↓n$ and $V↓n$
in (14) and outputs the value of $W↓n$ in (15), for $n = 1$,
2, 3, $\ldotss$, $N$. An auxiliary matrix $T↓{mn}$, $1 ≤ m ≤ n ≤
N$, is used in the calculations.

\algstep T1. [Initialize.] Set $n ← 1$. Let
the first two inputs (namely, $U↓1$ and $V↓1$) be stored in
$T↓{11}$ and $V↓1$, respectively.\xskip (We must have $V↓1 = 1.$)

\algstep T2. [Output $W↓n$.] Output the value of $T↓{1n}$ (which
is $W↓n$).

\algstep T3. [Input $U↓n$, $V↓n$.] Increase $n$ by 1. If $n
> N$, the algorithm terminates; otherwise store the next two
inputs (namely $U↓n$ and $V↓n$) in $T↓{1n}$ and $V↓n$, respectively.

\algstep T4. [Multiply.] Set
$$T↓{mn} ← T↓{11}T↓{m-1,n-1} + T↓{12}T↓{m-1,n-2} +\cdots
+ T↓{1,n-m+1}T↓{m-1,m-1}$$
and $T↓{1n} ← T↓{1n} - V↓mT↓{mn}$,
for $2 ≤ m ≤ n$.\xskip $\biglp$After this step we have the conditions
$$t↑m = T↓{mm}z↑m + T↓{m,m+1}z↑{m+1} +\cdots + T↓{mn}z↑n
+ O(z↑{n+1}),\qquad 1 ≤ m ≤ n.\eqno(16)$$
It is easy to verify (16) by induction
for $m ≥ 2$, and when $m = 1$, we have $U↓n = T↓{1n} + V↓2T↓{2n}
+\cdots + V↓nT↓{nn}$ by (14) and (19).$\bigrp$\xskip Return to
step T2.\quad\blackslug

\yyskip Equation (16) explains the
mechanism of this algorithm, which is due to Henry C. Thacher,
Jr.\ [{\sl CACM \bf 9} (1966), 10--11]. The running time is essentially
the same as Algorithm L\null, but considerably more storage space
is required. An example of this algorithm is worked in exercise 9.
\vfill\eject
\setcount0 801
\runninglefthead{ANSWERS TO EXERCISES---FIRST PROOFS $\copyright$ 1978}
\runningrighthead{ANSWERS TO EXERCISES---FIRST PROOFS $\copyright$ 1978}
\section{4.x}
\ninepoint